
class Trie {
    public:
        vector<Trie *> children;
        bool isEnd;
        Trie() 
            :children(26), 
            isEnd(false)
        {
            
        }
        Trie *searchPrefix(string prefix)
        {
            Trie *cur = this;
            for (auto ch : prefix)
            {
                ch -= 'a';
                if (cur->children[ch] == nullptr)
                {
                    return nullptr;
                }
                cur = cur->children[ch];
            }
            return cur;
        }
        
        void insert(string word) 
        {
            Trie *cur = this;
            for (auto ch : word)
            {
                ch -= 'a'; //下标
                if (cur->children[ch] == nullptr)
                {
                    cur->children[ch] = new Trie();
                }
                cur = cur->children[ch];
            }
            cur->isEnd = true;
        }
    
        bool search(string word) 
        {
            Trie *node = this->searchPrefix(word);
            return node != nullptr && node->isEnd;
        }
        
        bool startsWith(string prefix) 
        {
            return this->searchPrefix(prefix) != nullptr;    
        }
    };
    

struct TrieTree
{
    string _word;
    unordered_map<char, TrieTree *> children;
    TrieTree()
        :_word("")
    {}

    static void insertTree(string word, TrieTree *root)   //这个是构建一条分支
    {
        TrieTree *cur = root;
        for (auto &e : word)
        {
            char ch = e;
            if (!cur->children.count(ch))
            {
                cur->children[ch] = new TrieTree();
            }
            cur = cur->children[ch];
        }
        cur->_word = word;
    }
};
class Solution {
public:
    int count;
    int n;
    int m;
    vector<vector<bool>> check;
    unordered_set<string> ret;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    void dfs(int i, int j, TrieTree *root, vector<vector<char>> &board, vector<string> &words)
    {
        if (root->_word.size() != 0) 
        {
            ret.insert(root->_word);
        }
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x < 0 || y < 0 || x >= n || y >= m) continue;
            if (check[x][y] == true) continue;
            char in = board[x][y];
            if (root->children.count(in))
            {
                check[x][y] = true;
                dfs(x, y, root->children[in], board, words);
                check[x][y] = false;
            }
        }
    }
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) 
    {
        n = board.size();
        m = board[0].size();
        count = words.size();
        check.resize(n, vector<bool>(m, false));
        TrieTree *root = new TrieTree();   
        for (auto &word : words)           //构建字典树
        {
            TrieTree::insertTree(word, root);
        }
        //
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                char in = board[i][j];
                if (root->children.count(in))
                {
                    check[i][j] = true;
                    dfs(i, j, root->children[in], board, words);
                    check[i][j] = false;
                }
            }
        }
        vector<string> ans(ret.begin(), ret.end());
        return ans;
    }
};